package leetcode_200;



/**
 *@author 周杨
 *ReverseWordsInAString_151 反转一个字符串中的所有单词  Input: "the sky is blue",
												 Output: "blue is sky the". 其中去除所有无效空格
 *describe:方法1 用数组存储将要转成字符串的字符数组 用指针扫描前后
 *		      方法2  先把无效空格去除 反转字符串 然后再反转单词  AC 65%
 *		      方法3 用split方法把字符串分割 用StringBuilder添加到结果中 AC 90% 
 *2018年6月6日 上午10:08:04
 */
public class ReverseWordsInAString_151 {
	int index1,index2;
	public static void main(String[] args) {
		ReverseWordsInAString_151 test=new ReverseWordsInAString_151();
		System.out.println(test.scanLength("  a b c  d    "));
		System.out.println(test.reverseWords("  a b xa c  d    "));
		System.out.println(test.reverseWords("the sky is blue"));
		System.out.println(test.reverseWords("   a   b "));

	}
	
	public String reverseWords(String s) {
        int len=scanLength(s);
        char[] array=new char[len];
        int word1Left=index1,word1End=index1,word2Left=index2,word2End=word2Left;
        int arrayIndex1=0,arrayIndex2=array.length-1;
        while(word1End<word2Left) {
        	while(word1End<s.length()&&s.charAt(word1End)!=' ') {//扫描左边的单词
        		++word1End;
        	}
        	while(word2Left>=0&&s.charAt(word2Left)!=' ') {//扫描右边的单词
        		--word2Left;
        	}
        	if(word1End<=word2Left) {
        		for(int i=word1End-1;i>=word1Left;--i) {
        			array[arrayIndex2]=s.charAt(i);
        			--arrayIndex2;
        		}
        		for(int i=word2Left+1;i<=word2End;++i) {
        			array[arrayIndex1]=s.charAt(i);
        			++arrayIndex1;
        		}
        		if(arrayIndex1<arrayIndex2) {
	        		array[arrayIndex1++]=' ';
	        		if(arrayIndex1!=arrayIndex2){
	        			array[arrayIndex2--]=' ';
	        		}
        		}
        		for(int i=word1End;i<s.length();++i)
        			if(s.charAt(i)!=' ') {
        				word1Left=i;
        				word1End=i;
        				break;
        			}
        		for(int i=word2Left;i>=0;--i)
        			if(s.charAt(i)!=' ') {
        				word2End=i;
        				word2Left=i;
        				break;
        			}
        	}
        	else {
        		if(arrayIndex1<arrayIndex2) {
        			for(int i=word2Left+1;i<=word2End;++i) {
            			array[arrayIndex1]=s.charAt(i);
            			++arrayIndex1;
            		}
        		}
        	}
        }
		return String.copyValueOf(array);
    }
	
	/**
	 * describe:去除前导空格和后导空格 给每个单词预留一个空格 然后返回结果的整体长度
	 * 2018年6月5日 下午10:00:33
	 */
	public int scanLength(String s) {
		boolean flag=true;
		int res=0;
		this.index1=0;this.index2=s.length()-1;//去除空格
		while(index1<s.length()) {
			if(s.charAt(index1)==' ')
				++index1;
			else
				break;
		}
		while(index2>=0) {
			if(s.charAt(index2)==' ')
				--index2;
			else
				break;
		}
		if(index1<index2) {
			for(int i=index1;i<=index2;++i) {
				if(' '==s.charAt(i)) {
					if(flag) {//该字符做数
						++res;
						flag=false;
					}
				}
				else{
					++res;
					flag=true;
				}
			}
		}
		return res;
	}

}
